#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@sharp>
#
# Distributed under terms of the MIT license.

"""

"""

# class LinkNode:

# LRUCache(3)
# set(1, 1)
# set(2, 2)
# set(3, 3)
# set(3, 3)
# get(3)
# get(3)
# get(2)
# get(1)
# set(5, 5)
# get(1)
# get(2)
# get(3)
# get(3)
# get(5)
# 您的打印日志
# id n 140282061632456 1
# head 1 1 n 2 2
# tail 1 1 n 2 2
# head 2 2 n 3 3
# 2 140282061632680
# tail 1 1 n 3 3
# head 3 3 n 3 3
# tail 2 2 n 3 3
# head 3 3 n 2 2
# tail 3 3 n 2 2
# head 2 2 n 5 5
# 2 140282061632680
# tail 3 3 n 5 5
# head 5 5 n 3 3
# tail 3 3 n 3 3
# head 3 3 n 3 3
# tail 2 2 n 3 3
# head 3 3 n 5 5
# tail 2 2 n 5 5
# 输出
# [3,3,2,-1,-1,-1,3,3,5]
# 期望答案
# [3,3,2,-1,-1,2,3,-1,5]
# 提示
# 请检查你的代码和算法正确性，WA通常是由错误的答案造成的，请思考一下你的算法是否正确。

class Node:
    def __init__(self, key, value, pre=None, next=None):
        self.key = key
        self.value = value

        if pre is None:
            pre = self
        if  next is None:
            next = self

        self.pre = pre
        self.next = next

    # def set_loop(self):
    #     self.pre = self
    #     self.next = self

    def link(self, other):
        self.next = other
        other.pre = self


    def show(self):
        return self.key


class DoubleLinkedList:
    def __init__(self):
        self.pseudo_head = Node(-999, -999)
        self.len = 0

    @property
    def cur_head(self):
        return self.pseudo_head.next

    @property
    def cur_tail(self):
        return self.pseudo_head.pre

    def add_head(self, n):
        # 把n添加到head
        assert n is not None
        n.link(self.cur_head)

        self.pseudo_head.link(n)
        self.len += 1


    def del_tail(self):
        return self.del_node(self.cur_tail)

    def del_node(self, n):
        # 删除link 中的节点
        assert n is not self.pseudo_head
        assert n is not None

        pre = n.pre
        next = n.next
        pre.link(next)
        self.len -= 1
        return n

    def adjust_to_head(self, n):
        # 无论n在头部, 尾部, 中间
        # 无论链表有一个, 两个, 多个元素
        # 都要保证工作正确
        assert n is not self.pseudo_head
        assert n is not None
        self.del_node(n)
        self.add_head(n)

    def valid_and_show(self):
        assert self.cur_head.pre is self.pseudo_head
        assert self.cur_tail.next is self.pseudo_head

        assert self.pseudo_head.next is self.cur_head
        assert self.pseudo_head.pre is self.cur_tail

        cur = self.cur_head
        while cur is not self.pseudo_head:
            print(cur.show(), sep=' ', end=', ')
            cur = cur.next

        print("  | len is ", self.len)


class LRUCache:
    """
    @param: capacity: An integer
    """
    def __init__(self, capacity):
        self.capacity = capacity

        self.link = DoubleLinkedList()
        self.hash = {}      # {key: node}

    @property
    def len(self):
        assert self.link.len == len(self.hash)
        # return len(self.hash)
        return self.link.len

    def get(self, key):
        n = self.hash.get(key)
        if n is None:
            return -1

        result = n.value
        self.adjust_to_head(n)
        return result

    def set(self, key, value):
        n = self.hash.get(key)

        if n is None:
            n = Node(key, value)
            self.add_new_head(n)
            # self.hash[key] = n
        else:
            self.adjust_to_head(n)
            n.value = value

    def adjust_to_head(self, n):
        self.link.adjust_to_head(n)

    def add_new_head(self, n):
        if self.len >= self.capacity:
            # self.link.del_tail()
            self.del_tail()

        self.link.add_head(n)
        self.hash[n.key] = n

        self.valid()

    def del_tail(self):
        tail = self.link.del_tail()
        del self.hash[tail.key]
        # print('del tail ', tail.key)

    def valid(self):
        # print(len(self.hash), self.link.len)
        assert len(self.hash) == self.link.len

    # def self.del_tail(self):


def test():
    s = LRUCache(2)
    s.set(2, 222)
    # print('get 2', s.get(2))
    s.set(1, 111)

    print('get 1', s.get(1))
    print('get 2', s.get(2))
    print('get 1', s.get(1))

    s.set(3, 333)

    print(s.get(1))
    print(s.get(2))
    print(s.get(3))

    s.set(5, 555)
    print('get 2', s.get(2))
    print('get 3', s.get(3))
    print('get 5', s.get(5))

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
